// https://www.lintcode.com/problem/jump-game/my-submissions

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    // bool canJump(vector<int> &A) {
    //     vector<bool> result(A.size());
    //     result[0] = true;
    //     for (int i = 0; i < A.size(); ++i)
    //     {
    //         if (result[i])
    //         {
    //             for (int j = i; j <= i + A[i]; ++j)
    //             {
    //                 result[j] = true;
    //             }
    //         }
    //     }
    //     return result.back();
    // }
    
    // 按转移方程来：OR0<=i<j(f[i] AND i+a[i]>=j)
    bool canJump(vector<int> &A) {
        vector<bool> result(A.size(), false);
        result[0] = true;
        for (int i = 1; i < A.size(); ++i)
        {
            // previous stone j
            // last jump is from j to i
            for (int j = 0; j < i; ++j)
            {
                if (result[j] && j + A[j] >= i)
                    result[i] = true;
            }
        }
        return result[A.size() - 1];
    }
};